package com.wtgroup.demo.mianshi.算法.排序;

/**归并排序
 * @author L&J
 * @version 0.0.0
 * @email liuhejun108@163.com
 * @date 2019/9/9 10:10
 */
public class MergeSort implements ComparableSort{

    public static void sort( Comparable[] arr ){
        mergeSort(arr, 0, arr.length-1);
    }

    private static void mergeSort(Comparable[] arr, int left, int right) {
        if ( left>=right ) {
            return;
        }
        int mid = (left+right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, right, mid);

    }

    private static void merge( Comparable[] arr, int left, int right, int mid ) {

        // ArrayList<T> tmpLeft = new ArrayList<T>(mid - left + 2);
        // ArrayList<T> tmpRight      = new ArrayList<T>(right - mid + 1);
        int nL = mid - left + 1;
        int nR = right - mid;
        Comparable[] tmpLeft = new Comparable[nL];
        Comparable[] tmpRight = new Comparable[nR];
        for ( int i = 0; i < nL; i++ ) {
            tmpLeft[i] = arr[left + i];
        }
        for ( int i = 0; i < nR; i++ ) {
            tmpRight[i] = arr[mid + 1 + i];
        }
        // 泛型没法用哨兵机制了

        int k = left, l=0, r=0;
        while ( l<tmpLeft.length && r<tmpRight.length ) {
            int c = ((Comparable) tmpLeft[l]).compareTo(tmpRight[r]);
            if ( c > 0 ) {
                arr[k++] = tmpRight[r++];
            }else{
                arr[k++] = tmpLeft[l++];
            }
        }
        // 剩下的直接复制过去
        while ( l < tmpLeft.length ) {
            arr[k++] = tmpLeft[l++];
        }
        while ( r < tmpRight.length ) {
            arr[k++] = tmpRight[r++];
        }
    }


}
